1 Introduction

Following:
1. Wickham - Grolemund on Models

2.https://www.kdnuggets.com/2017/10/learn-generalized-linear-models-glm-r.html
and thereafter:

3.https://www.r-bloggers.com/how-to-perform-ordinal-logistic-regression-in-r/

2 Model Basics

gf_point(data = sim1, y ~ x)


# Trying models
models <- tibble(a1 = runif(250, -20, 50),
                 a2 = runif(250, -5,5))
gf_point(y ~x, data = sim1) %>% 
  gf_abline(intercept = ~a1, slope = ~a2, data = models,alpha = 0.3)

We can try to see how good any particular model is by the following:

# Choosing:
slope <- 2.5
intercept <- 1.5
# Add predictions with this model
sim1 <- sim1 %>% mutate(pred_y = intercept + slope * x)
# Plot distances
gf_jitter(y ~ x,width = 0.1, data = sim1) %>%
  gf_abline(
    intercept = ~ intercept,
    slope = ~ slope,
    color = "blue", data = sim1) %>% 
  gf_point(pred_y ~ x, data = sim1,color = "red") %>%
  gf_segment(pred_y + y ~ x + x, data = sim1)

# Compute distances
model1 <- function(a,data){
  a[1] + a[2]* data$x
}

model1(c(intercept, slope), sim1)
 [1]  4.0  4.0  4.0  6.5  6.5  6.5  9.0  9.0  9.0 11.5 11.5 11.5 14.0
[14] 14.0 14.0 16.5 16.5 16.5 19.0 19.0 19.0 21.5 21.5 21.5 24.0 24.0
[27] 24.0 26.5 26.5 26.5
# Distance measure of the MODEL
measure_distance <- function(mod,data){
  diff <- data$y - model1(mod, data)
  sqrt(mean(diff^2))
}
measure_distance(c(intercept,slope), sim1)
[1] 2.501
# using `purrr` to compute distance measures for all 250 models
# we need to fix the distance computation into a helper function specifically for our data.
# `measure_distance` also has a data frame to be passed as a parameter, which we cannot do with our `purrr` command.
sim1_dist <- function(a1,a2){
  measure_distance(c(a1,a2),sim1)
}

models <- models %>% 
  mutate(dist = purrr::map2_dbl(a1,a2,sim1_dist))
models

Now we can plot the 10 best models by ranking the models by the dist parameter.

gf_point(y~x, color = "grey30",data = sim1) %>% 
  gf_abline(intercept = ~ a1,slope = ~ a2, color = ~ dist, data = filter(models, rank(dist) <= 10))

We can also see a scatter plot of the parameters a1 and a2

gf_point( a1~ a2, data = filter(models, rank(dist)<=10), size = 4, color = "red") %>% 
  gf_point(a1 ~ a2, color = ~ -dist,data = models)

There could be a systematic search for models, by using a grid of points in the model space:

grid <- expand.grid(a1 = seq(-5, 10, length = 25),
                    a2 = seq(1.5,2.5,length = 25)) %>% 
  mutate(dist = purrr::map2_dbl(a1, a2, sim1_dist))

gf_point(a2 ~a1, data = filter(grid, rank(dist) <=10), color = "red", size = 4) %>% 
  gf_point(a2~a1, color = ~-dist, data = grid)

Aside: The Relationship between plotting the model parameter space and plotting models on the variable space is like the relationship between the Mandelbrot fractal and the Julia fractals.

Overlaying these 10 best models on the original data:

gf_point( y ~ x, data = sim1) %>% 
  gf_abline(intercept = ~a1, slope = ~ a2, color = ~ dist, data = filter(grid, rank(dist)<=10))

Rather than search through ever finer grids, we can use optimization in R to find the “best” model parameters a1, and a2.

best <- optim(par = c(0,0),fn = measure_distance, data = sim1)
best
$par
[1] 4.222 2.051

$value
[1] 2.128

$counts
function gradient 
      77       NA 

$convergence
[1] 0

$message
NULL
sim_mod <- lm(y~x, data = sim1)
sim_mod

Call:
lm(formula = y ~ x, data = sim1)

Coefficients:
(Intercept)            x  
       4.22         2.05

2.1 Adding Predictions

We can add a grid of data points to cover exactly the range of the variables we have in our dataset.

grid <- modelr::data_grid(data = sim1, x)
grid

# Add Predictions
grid <- grid %>% add_predictions(model = sim_mod, var = "pred")
grid

# Plot this
gf_point(y~x, data = sim1) %>% 
  gf_line(pred~x,data = grid,color = "red", size = 2)

We can add residuals to the original data frame using modelr

sim1 <- sim1 %>% add_residuals(model = sim_mod)
sim1

# Plotting the residuals
gf_point(data = sim1, resid~x) %>% gf_hline(yintercept = ~ 0)

gf_density(data = sim1, ~resid)

Frequency spread of the residuals looks reasonable. No regular pattern “left over” in the residuals.

3 Model Families

The model_matrix() function: >It takes a data frame and a formula and returns a tibble that defines the model equation: each column in the output is associated with one coefficient in the model, the function is always y = a_1 * out1 + a_2 * out_2.

3.1 Categorical Variables

We use the sim2 dataset to explore this.


sim2 %>% gf_point(y~x)


# Model fitting
mod2 <- lm(y~x, data = sim2)

grid <- sim2 %>% data_grid(x) %>% add_predictions(mod2)
grid

# Plot the model on the data
gf_point(y~x, data = sim2) %>% 
  gf_point(pred~x,data = grid, color = "red",size = 4)

With a categorical variable for x, we predict the mean value for each category with our model.

3.2 Interaction: Continuous and Categorical variable

sim3

gf_point(y~x1, data = sim3, color = ~x2)

We can fit two kinds of models: with and without interactions

mod1 = lm(y ~ x1 + x2, data = sim3)
mod2 = lm(y ~ x1 * x2, data = sim3)

# Use data_grid
grid <- sim3 %>% data_grid(x1,x2) %>% gather_predictions(mod1,mod2)
grid
sim3 %>% 
  gf_point(y ~ x1, color = ~x2, data = sim3) %>% 
  gf_line(pred ~ x1 | model, data = grid)

Recall the discussion in Chester Ismay’s Modern Dive. mod1 uses the same slope for both models and only varies the intercept, whereas mod2 varies both model parameters.

We can check which model is better by plotting residuals.

sim3 %>% gather_residuals(mod1, mod2) %>% 
  gf_point(resid ~ x1|model ~ x2, color = ~x2, data = sim3)

mod2 residuals have no pattern and look random. mod1 residuals do have patterns, especially for category b.

3.3 Interaction: Two Continuous Variables

As in the last section we can explore two kinds of models, with and wthout interaction.

sim4

mod1 <- lm( y ~ x1 + x2, data = sim4)
mod2 <- lm( y ~ x1 * x2, data = sim4)

# Visualisation
grid <- sim4 %>% 
  data_grid(x1 = seq_range(x1,n = 5,pretty = TRUE), 
            x2 = seq_range(x2, 5,pretty = TRUE)) %>% 
  gather_predictions(mod1, mod2)
# seq_range is a modelr command, ot generate n numbers spaced over the range of a variable. 
grid

# Visualisation
gf_tile(x2 ~ x1 | model, fill = ~ pred, data = grid )

Can’t see much difference there….

gf_line(pred ~ x1 | model, color =  ~ x2, group = ~ x2, data = grid) %>% gf_refine(scale_color_distiller(palette = 7))


gf_line(pred ~ x2 |~ model, color = ~ x1, group = ~ x1, data = grid)

Let’s look at the residuals…

sim4 %>% 
  gather_residuals(mod1, mod2) %>% 
  gf_point(resid ~ x1|model ~ x2, color = ~x2, data = sim4)


# What plot can we use to show which model is better?
sim4 %>% 
  gather_residuals(mod1, mod2) %>% 
  gf_point(mean(abs(resid))~ x1 | model ~ x2, color = ~ x2, data = .)

# NEEDS MORE IMAGINATION AND WORK!!

3.4 Transformation while Modelling

Data variables can also be algebraically transformed while putting them into the model. Actual arithmetic operators like + and * should be wrapped in I() to ensure that they are interpreted correctly. It is always good to check with model_matrix what the model is doing, so that we know what we are getting. > Note we can do the modelling itself inside the model_matrix command!

df <- tribble(~y, ~x, 1,1,2,2,3,3)

model_matrix(df, y ~ x^2 + x)
# This uses the Wilkinson-Rogers Notation !!

model_matrix(df, y ~ I(x^2) + x)
# Can also use I(x^2 + x)

There are many transformations possible Using Taylor’s series is one way

model_matrix(df, y ~ poly(x, 2))

poly fits the data well within the range; outside, when it is extrapolating, it may may shoot off to infinity. In this case it is better to use natural splines, which is somewhat better, though it still makes errors outside the data range.

library(splines)
model_matrix(df, y ~ ns(x, 2))

Let us model nonlinear data.

sim5 <- tibble(x = seq(0, 3.5 * pi, length = 50),
               y = 4 * sin(x) + rnorm(length(x)))
gf_point(y ~ x, data = sim5)


# We can fit multiple models to this data
mod1 <- lm(y ~ ns(x, 1), data = sim5)
mod2 <- lm(y ~ ns(x, 2), data = sim5)
mod3 <- lm(y ~ ns(x, 3), data = sim5)
mod4 <- lm(y ~ ns(x, 4), data = sim5)
mod5 <- lm(y ~ ns(x, 5), data = sim5)

grid <- sim5 %>% 
  data_grid(x = seq_range(x,n = 50,expand = 0.1)) %>% 
  gather_predictions(mod1,mod2,mod3,mod4,mod5, .pred = "y")

# Plotting the 5 models
 gf_point(data = sim5, y ~ x) %>% 
   gf_line(data = grid, y ~ x | model, color = ~model) 

NA

Notice that the extrapolation outside the range of the data is clearly bad. This is the downside to approximating a function with a polynomial. But this is a very real problem with every model: the model can never tell you if the behaviour is true when you start extrapolating outside the range of the data that you have seen. You must rely on theory and science.

3.5 Other Model Families

  1. ** Generalised Linear models:** stats::glm() extend linear models to count or binary response variables. Use a different metric for distance.

  2. ** Generalised Additive Models:** mgcv::gam() can use arbitrary smooth modelling functions like y ~ s(x). gam() will estimate the function. (Rather like the regression software I used earlier.)

  3. ** Penalised Linear Models:** glmnet::glmnet() Adds a penalty vector in parameter space corresponding to distance of that vector from the origin. Tends to make models generalise better to new datasets from the population.

  4. ** Robust Linear Models:** MASS::rlm() tweaks the distance metric to down-weight data points that are far away, i.e. outliers. Less sensitive to outliers, but not so good when there are no outliers.

  5. ** Trees:** Fit piece-wise linear models to smaller and smaller pieces of data ( like a Lindenmayer fractal). Work best when used in aggregate models like randomForest::randomForest() and gradient boost xgboost::xgboost().

A Generalized Linear Model (GLM/GLZ) helps represent the dependent variable as a linear combination of independent variables. In its simplest form, a linear model specifies the (linear) relationship between a dependent (or response) variable Y, and a set of predictor variables, the X’s, so that

\[ Y = b_0 + b_1X_1 + b_2X_2 + ... + b_kX_k + e \]

In the GLZs, the model is assumed to be: \[ Y = g (b_0 + b_1X_1 + b_2X_2 + ... + b_kX_k )+ e \] The inverse of the funtion g(...), say f(…)is called thelink function`, so that:

\[ f(\mu_Y)= b_0 + b_1X_1 + b_2X_2 + ... + b_kX_k \]

GLZs work when :

  1. the dependent variable has a discrete/multinomial distribution. The distribution of the dependent or response variable can be (explicitly) non-normal, and does not have to be continuous, i.e., it can be binomial, multinomial, or ordinal multinomial (i.e., contain information on ranks only);

  2. the relationship between dependent and independent variable (i.e. the link function) is inherently nonlinear, or a power relationship, for example.

4 CocaCola Sales Data Exploration

# Temperature vs CocaCola sales
cola <- read_csv("./cola.csv")
Parsed with column specification:
cols(
  Temperature = col_double(),
  Cola = col_double()
)
penalty <- read_csv("./penalty.csv")
Parsed with column specification:
cols(
  Practice = col_double(),
  Outcome = col_double()
)
str(cola)
Classes ‘spec_tbl_df’, ‘tbl_df’, ‘tbl’ and 'data.frame':    48 obs. of  2 variables:
 $ Temperature: num  1 2 3 4 5 6 7 8 9 10 ...
 $ Cola       : num  1 1 1 1 1 1 1 1 2 2 ...
 - attr(*, "spec")=
  .. cols(
  ..   Temperature = col_double(),
  ..   Cola = col_double()
  .. )
gf_point(Cola ~ Temperature, data = cola)

4.1 Linear Model Fitting


model =lm(data = cola, Cola ~ Temperature)
gf_point(Cola ~ Temperature, data = cola) %>% 
  gf_abline(intercept = ~model$coefficients[1],
            slope = ~model$coefficients[2],data = cola)


#Calculate RMSE
PredCola <- predict(model, cola)
RMSE <- modelr::rmse(model, cola)
##
model

Call:
lm(formula = Cola ~ Temperature, data = cola)

Coefficients:
(Intercept)  Temperature  
       -278           20  
RMSE
[1] 241.5

The linear model is clearly inadequate and makes faulty predictions. We try to use a log-linear model next, since the Cola sales figure seems to have an exponential relationship with Temperature. We see that: \[Cola = a * b ^ {Temperature} ....Eqn(1)\]

Such growth models depict a variety of real life situations and can be modeled using log-linear regression. Apart from exponential relationship, log transformation on (the) dependent variable is also used when dependent variable follows: a) log-normal distribution - log-normal distribution is distribution of a random variable whose log follows normal distribution. Thus, taking log of a log-normal random variable makes the variable normally distributed and fit for linear regression.
b) Poisson distribution - Poisson distribution is the distribution of random variable that results from a Poisson experiment. For example, the number of successes or failures in a time period T follows Poisson distribution.

Taking log on both sides of Eqn.1:

\[log(Cola) = log(a) + Temperature * log(b)\]

4.2 Log Model Fitting

We transform the data using log and then fit a linear model to the log-transformed variables

cola <- cola %>% mutate(logCola = log(Cola))

logmodel <- lm(logCola ~ Temperature, data = cola)
logmodel

Call:
lm(formula = logCola ~ Temperature, data = cola)

Coefficients:
(Intercept)  Temperature  
     -0.909        0.172  
# Plots
gf_point(data = cola, logCola~Temperature) %>% 
  gf_abline(intercept = ~logmodel$coefficients[1],slope = ~logmodel$coefficients[2])


# Predictions and RMSE
PredLogCola <- predict(logmodel,cola)
RMSElog <- modelr::rmse(logmodel, cola)

PredLogCola
       1        2        3        4        5        6        7 
-0.73672 -0.56445 -0.39217 -0.21989 -0.04762  0.12466  0.29694 
       8        9       10       11       12       13       14 
 0.46921  0.64149  0.81377  0.98605  1.15832  1.33060  1.50288 
      15       16       17       18       19       20       21 
 1.67515  1.84743  2.01971  2.19198  2.36426  2.53654  2.70881 
      22       23       24       25       26       27       28 
 2.88109  3.05337  3.22564  3.39792  3.57020  3.74248  3.91475 
      29       30       31       32       33       34       35 
 4.08703  4.25931  4.43158  4.60386  4.77614  4.94841  5.12069 
      36       37       38       39       40       41       42 
 5.29297  5.46524  5.63752  5.80980  5.98207  6.15435  6.32663 
      43       44       45       46       47       48 
 6.49891  6.67118  6.84346  7.01574  7.18801  7.36029 
RMSElog
[1] 0.2466

Hence the log-linear model is:

\[ log(Cola_i) = -0.909 + 0.172 * log(Temperature_i) \]

str(PredLogCola)
 Named num [1:48] -0.7367 -0.5644 -0.3922 -0.2199 -0.0476 ...
 - attr(*, "names")= chr [1:48] "1" "2" "3" "4" ...
gf_col(data = PredLogCola,value ~ row_number(PredLogCola))
Error: `data` must be a data frame, or other object coercible by `fortify()`, not a numeric vector
LS0tCnRpdGxlOiAiR2VuZXJhbGl6ZWQgTGluZWFyIE1vZGVscyIKb3V0cHV0OiAKICBodG1sX25vdGVib29rOgogICAgZmlnX2NhcHRpb246IHllcwogICAgbnVtYmVyX3NlY3Rpb25zOiB5ZXMKICAgIHRoZW1lOiBjZXJ1bGVhbgogICAgdG9jOiB5ZXMKICBnaXRodWJfZG9jdW1lbnQ6IGRlZmF1bHQKICBodG1sX2RvY3VtZW50OiBkZWZhdWx0CiAgcGRmX2RvY3VtZW50OgogICAgbGF0ZXhfZW5naW5lOiB4ZWxhdGV4Ci0tLQpgYGB7ciBzZXQgdXAsIG1lc3NhZ2U9RkFMU0UsZWNobz1GQUxTRSxjYWNoZT1UUlVFfQpsaWJyYXJ5KHRpZHl2ZXJzZSkKbGlicmFyeShtb2RlbHIpCmxpYnJhcnkoZ2dmb3JtdWxhKQpsaWJyYXJ5KHBsYW50dW1sKSAjIGZvciBkb2N1bWVudGF0aW9uCmxpYnJhcnkoRGlhZ3JhbW1lUikgIyBmb3IgZG9jdW1lbnRhdGlvbgojIHVwZGF0ZVBsYW50dW1sSmFyKCkKYGBgCgoKIyBJbnRyb2R1Y3Rpb24KRm9sbG93aW5nOiAgCjEuIFdpY2toYW0gLSBHcm9sZW11bmQgb24gW01vZGVsc10oaHR0cHM6Ly9yNGRzLmhhZC5jby5uei9tb2RlbC1iYXNpY3MuaHRtbCkKCjIuPGh0dHBzOi8vd3d3LmtkbnVnZ2V0cy5jb20vMjAxNy8xMC9sZWFybi1nZW5lcmFsaXplZC1saW5lYXItbW9kZWxzLWdsbS1yLmh0bWw+ICAKYW5kIHRoZXJlYWZ0ZXI6CgozLjxodHRwczovL3d3dy5yLWJsb2dnZXJzLmNvbS9ob3ctdG8tcGVyZm9ybS1vcmRpbmFsLWxvZ2lzdGljLXJlZ3Jlc3Npb24taW4tci8+ICAKCiMgTW9kZWwgQmFzaWNzCiAtICoqRmFtaWx5IG9mIE1vZGVscyoqIC0gcmVwcmVzZW50cyBhIGdlbmVyYWwgcmVsYXRpb25zaGlwIG9yIHBhdHRlcm4gYmV0d2VlbiB2YXJpYWJsZXMgaW4geW91ciBkYXRhCiAtICoqRml0dGVkIE1vZGVsKiogZmluZGluZyBhIG1vZGVsIGZyb20gdGhlIGZhbWlseSB0aGF0IGlzIGNsb3Nlc3QgdG8geW91ciBkYXRhOyBpdCBpcyAiYmVzdCIgYWNjb3JkaW5nIHRvIHNvbWUgY3JpdGVyaWEuIAoKYGBge3Igc2ltMX0KZ2ZfcG9pbnQoZGF0YSA9IHNpbTEsIHkgfiB4KQoKIyBUcnlpbmcgbW9kZWxzCm1vZGVscyA8LSB0aWJibGUoYTEgPSBydW5pZigyNTAsIC0yMCwgNTApLAogICAgICAgICAgICAgICAgIGEyID0gcnVuaWYoMjUwLCAtNSw1KSkKZ2ZfcG9pbnQoeSB+eCwgZGF0YSA9IHNpbTEpICU+JSAKICBnZl9hYmxpbmUoaW50ZXJjZXB0ID0gfmExLCBzbG9wZSA9IH5hMiwgZGF0YSA9IG1vZGVscyxhbHBoYSA9IDAuMykKYGBgCgpXZSBjYW4gdHJ5IHRvIHNlZSBob3cgZ29vZCBhbnkgcGFydGljdWxhciBtb2RlbCBpcyBieSB0aGUgZm9sbG93aW5nOgoKYGBge3Igc2VlaW5nIGRpc3RhbmNlc30KIyBDaG9vc2luZzoKc2xvcGUgPC0gMi41CmludGVyY2VwdCA8LSAxLjUKIyBBZGQgcHJlZGljdGlvbnMgd2l0aCB0aGlzIG1vZGVsCnNpbTEgPC0gc2ltMSAlPiUgbXV0YXRlKHByZWRfeSA9IGludGVyY2VwdCArIHNsb3BlICogeCkKIyBQbG90IGRpc3RhbmNlcwpnZl9qaXR0ZXIoeSB+IHgsd2lkdGggPSAwLjEsIGRhdGEgPSBzaW0xKSAlPiUKICBnZl9hYmxpbmUoCiAgICBpbnRlcmNlcHQgPSB+IGludGVyY2VwdCwKICAgIHNsb3BlID0gfiBzbG9wZSwKICAgIGNvbG9yID0gImJsdWUiLCBkYXRhID0gc2ltMSkgJT4lIAogIGdmX3BvaW50KHByZWRfeSB+IHgsIGRhdGEgPSBzaW0xLGNvbG9yID0gInJlZCIpICU+JQogIGdmX3NlZ21lbnQocHJlZF95ICsgeSB+IHggKyB4LCBkYXRhID0gc2ltMSkKYGBgCgoKYGBge3IgY29tcHV0ZSBkaXN0YW5jZXN9CiMgQ29tcHV0ZSBkaXN0YW5jZXMKbW9kZWwxIDwtIGZ1bmN0aW9uKGEsZGF0YSl7CiAgYVsxXSArIGFbMl0qIGRhdGEkeAp9Cgptb2RlbDEoYyhpbnRlcmNlcHQsIHNsb3BlKSwgc2ltMSkKCiMgRGlzdGFuY2UgbWVhc3VyZSBvZiB0aGUgTU9ERUwKbWVhc3VyZV9kaXN0YW5jZSA8LSBmdW5jdGlvbihtb2QsZGF0YSl7CiAgZGlmZiA8LSBkYXRhJHkgLSBtb2RlbDEobW9kLCBkYXRhKQogIHNxcnQobWVhbihkaWZmXjIpKQp9Cm1lYXN1cmVfZGlzdGFuY2UoYyhpbnRlcmNlcHQsc2xvcGUpLCBzaW0xKQoKCiMgdXNpbmcgYHB1cnJyYCB0byBjb21wdXRlIGRpc3RhbmNlIG1lYXN1cmVzIGZvciBhbGwgMjUwIG1vZGVscwojIHdlIG5lZWQgdG8gZml4IHRoZSBkaXN0YW5jZSBjb21wdXRhdGlvbiBpbnRvIGEgaGVscGVyIGZ1bmN0aW9uIHNwZWNpZmljYWxseSBmb3Igb3VyIGRhdGEuCiMgYG1lYXN1cmVfZGlzdGFuY2VgIGFsc28gaGFzIGEgZGF0YSBmcmFtZSB0byBiZSBwYXNzZWQgYXMgYSBwYXJhbWV0ZXIsIHdoaWNoIHdlIGNhbm5vdCBkbyB3aXRoIG91ciBgcHVycnJgIGNvbW1hbmQuCnNpbTFfZGlzdCA8LSBmdW5jdGlvbihhMSxhMil7CiAgbWVhc3VyZV9kaXN0YW5jZShjKGExLGEyKSxzaW0xKQp9Cgptb2RlbHMgPC0gbW9kZWxzICU+JSAKICBtdXRhdGUoZGlzdCA9IHB1cnJyOjptYXAyX2RibChhMSxhMixzaW0xX2Rpc3QpKQptb2RlbHMKYGBgCgoKTm93IHdlIGNhbiBwbG90IHRoZSAxMCBiZXN0IG1vZGVscyBieSByYW5raW5nIHRoZSBgbW9kZWxzYCBieSB0aGUgYGRpc3RgIHBhcmFtZXRlci4gCgpgYGB7ciBwbG90dGluZyB0aGUgMTAgYmVzdH0KZ2ZfcG9pbnQoeX54LCBjb2xvciA9ICJncmV5MzAiLGRhdGEgPSBzaW0xKSAlPiUgCiAgZ2ZfYWJsaW5lKGludGVyY2VwdCA9IH4gYTEsc2xvcGUgPSB+IGEyLCBjb2xvciA9IH4gZGlzdCwgZGF0YSA9IGZpbHRlcihtb2RlbHMsIHJhbmsoZGlzdCkgPD0gMTApKQpgYGAKCldlIGNhbiBhbHNvIHNlZSBhIHNjYXR0ZXIgcGxvdCBvZiB0aGUgKipwYXJhbWV0ZXJzKiogYGExYCBhbmQgYGEyYApgYGB7ciBwbG90dGluZyB0aGUgcGFyYW1ldGVyc30KZ2ZfcG9pbnQoIGExfiBhMiwgZGF0YSA9IGZpbHRlcihtb2RlbHMsIHJhbmsoZGlzdCk8PTEwKSwgc2l6ZSA9IDQsIGNvbG9yID0gInJlZCIpICU+JSAKICBnZl9wb2ludChhMSB+IGEyLCBjb2xvciA9IH4gLWRpc3QsZGF0YSA9IG1vZGVscykKYGBgCgpUaGVyZSBjb3VsZCBiZSBhIHN5c3RlbWF0aWMgc2VhcmNoIGZvciBtb2RlbHMsIGJ5IHVzaW5nIGEgZ3JpZCBvZiBwb2ludHMgaW4gdGhlIGBtb2RlbCBzcGFjZWA6CmBgYHtyIEV4cGxvcmluZyB0aGUgTW9kZWwgU3BhY2V9CmdyaWQgPC0gZXhwYW5kLmdyaWQoYTEgPSBzZXEoLTUsIDEwLCBsZW5ndGggPSAyNSksCiAgICAgICAgICAgICAgICAgICAgYTIgPSBzZXEoMS41LDIuNSxsZW5ndGggPSAyNSkpICU+JSAKICBtdXRhdGUoZGlzdCA9IHB1cnJyOjptYXAyX2RibChhMSwgYTIsIHNpbTFfZGlzdCkpCgpnZl9wb2ludChhMiB+YTEsIGRhdGEgPSBmaWx0ZXIoZ3JpZCwgcmFuayhkaXN0KSA8PTEwKSwgY29sb3IgPSAicmVkIiwgc2l6ZSA9IDQpICU+JSAKICBnZl9wb2ludChhMn5hMSwgY29sb3IgPSB+LWRpc3QsIGRhdGEgPSBncmlkKQpgYGAKCkFzaWRlOiBUaGUgUmVsYXRpb25zaGlwIGJldHdlZW4gcGxvdHRpbmcgdGhlIG1vZGVsIHBhcmFtZXRlciBzcGFjZSBhbmQgcGxvdHRpbmcgbW9kZWxzIG9uIHRoZSB2YXJpYWJsZSBzcGFjZSBpcyBsaWtlIHRoZSByZWxhdGlvbnNoaXAgYmV0d2VlbiB0aGUgTWFuZGVsYnJvdCBmcmFjdGFsIGFuZCB0aGUgSnVsaWEgZnJhY3RhbHMuIAoKT3ZlcmxheWluZyB0aGVzZSAxMCBiZXN0IG1vZGVscyBvbiB0aGUgb3JpZ2luYWwgZGF0YToKCmBgYHtyIFBsb3R0aW5nIHRoZSAxMCBiZXN0fQpnZl9wb2ludCggeSB+IHgsIGRhdGEgPSBzaW0xKSAlPiUgCiAgZ2ZfYWJsaW5lKGludGVyY2VwdCA9IH5hMSwgc2xvcGUgPSB+IGEyLCBjb2xvciA9IH4gZGlzdCwgZGF0YSA9IGZpbHRlcihncmlkLCByYW5rKGRpc3QpPD0xMCkpCmBgYAoKUmF0aGVyIHRoYW4gc2VhcmNoIHRocm91Z2ggZXZlciBmaW5lciBncmlkcywgd2UgY2FuIHVzZSBvcHRpbWl6YXRpb24gaW4gUiB0byBmaW5kIHRoZSAiYmVzdCIgbW9kZWwgcGFyYW1ldGVycyBgYTFgLCBhbmQgYGEyYC4KCmBgYHtyIE9wdGltdW0gTW9kZWxzfQpiZXN0IDwtIG9wdGltKHBhciA9IGMoMCwwKSxmbiA9IG1lYXN1cmVfZGlzdGFuY2UsIGRhdGEgPSBzaW0xKQpiZXN0CnNpbV9tb2QgPC0gbG0oeX54LCBkYXRhID0gc2ltMSkKc2ltX21vZApgYGAKCiMjIEFkZGluZyBQcmVkaWN0aW9ucwoKV2UgY2FuIGFkZCBhIGBncmlkYCBvZiBkYXRhIHBvaW50cyB0byBjb3ZlciBleGFjdGx5IHRoZSByYW5nZSBvZiB0aGUgdmFyaWFibGVzIHdlIGhhdmUgaW4gb3VyIGRhdGFzZXQuIAoKYGBge3IgQWRkIFByZWRpY3Rpb25zfQpncmlkIDwtIG1vZGVscjo6ZGF0YV9ncmlkKGRhdGEgPSBzaW0xLCB4KQpncmlkCgojIEFkZCBQcmVkaWN0aW9ucwpncmlkIDwtIGdyaWQgJT4lIGFkZF9wcmVkaWN0aW9ucyhtb2RlbCA9IHNpbV9tb2QsIHZhciA9ICJwcmVkIikKZ3JpZAoKIyBQbG90IHRoaXMKZ2ZfcG9pbnQoeX54LCBkYXRhID0gc2ltMSkgJT4lIAogIGdmX2xpbmUocHJlZH54LGRhdGEgPSBncmlkLGNvbG9yID0gInJlZCIsIHNpemUgPSAyKQoKYGBgCgpXZSBjYW4gYWRkIHJlc2lkdWFscyB0byB0aGUgb3JpZ2luYWwgZGF0YSBmcmFtZSB1c2luZyBgbW9kZWxyYAoKYGBge3IgcmVzaWR1YWxzfQpzaW0xIDwtIHNpbTEgJT4lIGFkZF9yZXNpZHVhbHMobW9kZWwgPSBzaW1fbW9kKQpzaW0xCgojIFBsb3R0aW5nIHRoZSByZXNpZHVhbHMKZ2ZfcG9pbnQoZGF0YSA9IHNpbTEsIHJlc2lkfngpICU+JSBnZl9obGluZSh5aW50ZXJjZXB0ID0gfiAwKQpnZl9kZW5zaXR5KGRhdGEgPSBzaW0xLCB+cmVzaWQpCgpgYGAKCkZyZXF1ZW5jeSBzcHJlYWQgb2YgdGhlIHJlc2lkdWFscyBsb29rcyByZWFzb25hYmxlLiBObyByZWd1bGFyIHBhdHRlcm4gImxlZnQgb3ZlciIgaW4gdGhlIHJlc2lkdWFscy4gCgoKIyBNb2RlbCBGYW1pbGllcwpUaGUgYG1vZGVsX21hdHJpeCgpYCBmdW5jdGlvbjoKPkl0IHRha2VzIGEgZGF0YSBmcmFtZSBhbmQgYSBmb3JtdWxhIGFuZCByZXR1cm5zIGEgdGliYmxlIHRoYXQgZGVmaW5lcyB0aGUgbW9kZWwgZXF1YXRpb246IGVhY2ggY29sdW1uIGluIHRoZSBvdXRwdXQgaXMgYXNzb2NpYXRlZCB3aXRoIG9uZSBjb2VmZmljaWVudCBpbiB0aGUgbW9kZWwsIHRoZSBmdW5jdGlvbiBpcyBhbHdheXMgYHkgPSBhXzEgKiBvdXQxICsgYV8yICogb3V0XzJgLgoKIyMgQ2F0ZWdvcmljYWwgVmFyaWFibGVzCgpXZSB1c2UgdGhlIGBzaW0yYCBkYXRhc2V0IHRvIGV4cGxvcmUgdGhpcy4gCmBgYHtyIENhdGVnb3JpY2FsIEluZGVwZW5kZW50IFZhcmlhYmxlc30KCnNpbTIgJT4lIGdmX3BvaW50KHl+eCkKCiMgTW9kZWwgZml0dGluZwptb2QyIDwtIGxtKHl+eCwgZGF0YSA9IHNpbTIpCgpncmlkIDwtIHNpbTIgJT4lIGRhdGFfZ3JpZCh4KSAlPiUgYWRkX3ByZWRpY3Rpb25zKG1vZDIpCmdyaWQKCiMgUGxvdCB0aGUgbW9kZWwgb24gdGhlIGRhdGEKZ2ZfcG9pbnQoeX54LCBkYXRhID0gc2ltMikgJT4lIAogIGdmX3BvaW50KHByZWR+eCxkYXRhID0gZ3JpZCwgY29sb3IgPSAicmVkIixzaXplID0gNCkKYGBgCldpdGggYSBjYXRlZ29yaWNhbCB2YXJpYWJsZSBmb3IgYHhgLCB3ZSBwcmVkaWN0IHRoZSBgbWVhbmAgdmFsdWUgZm9yIGVhY2ggY2F0ZWdvcnkgd2l0aCBvdXIgbW9kZWwuCgoKIyMgSW50ZXJhY3Rpb246IENvbnRpbnVvdXMgYW5kIENhdGVnb3JpY2FsIHZhcmlhYmxlCgpgYGB7ciBJbnRlcmFjdGlvbiBDb250aW51b3VzIGFuZCBDYXRlZ29yaWNhbCBWYXJpYWJsZXN9CnNpbTMKCmdmX3BvaW50KHl+eDEsIGRhdGEgPSBzaW0zLCBjb2xvciA9IH54MikKYGBgCgpXZSBjYW4gZml0IHR3byBraW5kcyBvZiBtb2RlbHM6IHdpdGggYW5kIHdpdGhvdXQgaW50ZXJhY3Rpb25zCgpgYGB7ciBUd28ga2luZHMgb2YgbW9kZWxzfQptb2QxID0gbG0oeSB+IHgxICsgeDIsIGRhdGEgPSBzaW0zKQptb2QyID0gbG0oeSB+IHgxICogeDIsIGRhdGEgPSBzaW0zKQoKIyBVc2UgZGF0YV9ncmlkCmdyaWQgPC0gc2ltMyAlPiUgZGF0YV9ncmlkKHgxLHgyKSAlPiUgZ2F0aGVyX3ByZWRpY3Rpb25zKG1vZDEsbW9kMikKZ3JpZApgYGAKCmBgYHtyIFZpc3VhbGlzaW5nIGJvdGggbW9kZWxzfQpzaW0zICU+JSAKICBnZl9wb2ludCh5IH4geDEsIGNvbG9yID0gfngyLCBkYXRhID0gc2ltMykgJT4lIAogIGdmX2xpbmUocHJlZCB+IHgxIHwgbW9kZWwsIGRhdGEgPSBncmlkKQoKYGBgCgpSZWNhbGwgdGhlIGRpc2N1c3Npb24gaW4gQ2hlc3RlciBJc21heSdzIFtgTW9kZXJuIERpdmVgXSh3d3cubW9kZXJuLmRpdmUuY29tKS4gYG1vZDFgIHVzZXMgdGhlIHNhbWUgYHNsb3BlYCBmb3IgYm90aCBtb2RlbHMgYW5kIG9ubHkgdmFyaWVzIHRoZSBgaW50ZXJjZXB0YCwgd2hlcmVhcyBgbW9kMmAgdmFyaWVzIGJvdGggbW9kZWwgcGFyYW1ldGVycy4gCgpXZSBjYW4gY2hlY2sgd2hpY2ggbW9kZWwgaXMgYmV0dGVyIGJ5IHBsb3R0aW5nIHJlc2lkdWFscy4gCmBgYHtyIFJlc2lkdWFsczogSW50ZXJhdGlvbiBvciBub3R9CnNpbTMgJT4lIGdhdGhlcl9yZXNpZHVhbHMobW9kMSwgbW9kMikgJT4lIAogIGdmX3BvaW50KHJlc2lkIH4geDF8bW9kZWwgfiB4MiwgY29sb3IgPSB+eDIsIGRhdGEgPSBzaW0zKQpgYGAKYG1vZDJgIHJlc2lkdWFscyBoYXZlIG5vIHBhdHRlcm4gYW5kIGxvb2sgcmFuZG9tLiBgbW9kMWAgcmVzaWR1YWxzIGRvIGhhdmUgcGF0dGVybnMsIGVzcGVjaWFsbHkgZm9yIGNhdGVnb3J5IGBiYC4KCiMjIEludGVyYWN0aW9uOiBUd28gQ29udGludW91cyBWYXJpYWJsZXMKCkFzIGluIHRoZSBsYXN0IHNlY3Rpb24gd2UgY2FuIGV4cGxvcmUgdHdvIGtpbmRzIG9mIG1vZGVscywgd2l0aCBhbmQgd3Rob3V0IGludGVyYWN0aW9uLgpgYGB7ciBDb250aW51b3VzIGluZGVwZW5kZW50IFZhcmlhYmxlcyB3aXRoIEludGVyYWN0aW9ufQpzaW00Cgptb2QxIDwtIGxtKCB5IH4geDEgKyB4MiwgZGF0YSA9IHNpbTQpCm1vZDIgPC0gbG0oIHkgfiB4MSAqIHgyLCBkYXRhID0gc2ltNCkKCiMgVmlzdWFsaXNhdGlvbgpncmlkIDwtIHNpbTQgJT4lIAogIGRhdGFfZ3JpZCh4MSA9IHNlcV9yYW5nZSh4MSxuID0gNSxwcmV0dHkgPSBUUlVFKSwgCiAgICAgICAgICAgIHgyID0gc2VxX3JhbmdlKHgyLCA1LHByZXR0eSA9IFRSVUUpKSAlPiUgCiAgZ2F0aGVyX3ByZWRpY3Rpb25zKG1vZDEsIG1vZDIpCiMgc2VxX3JhbmdlIGlzIGEgbW9kZWxyIGNvbW1hbmQsIHRvIGdlbmVyYXRlIG4gbnVtYmVycyBzcGFjZWQgb3ZlciB0aGUgcmFuZ2Ugb2YgYSB2YXJpYWJsZS4gCmdyaWQKCiMgVmlzdWFsaXNhdGlvbgpnZl90aWxlKHgyIH4geDEgfCBtb2RlbCwgZmlsbCA9IH4gcHJlZCwgZGF0YSA9IGdyaWQgKQpgYGAKCkNhbid0IHNlZSBtdWNoIGRpZmZlcmVuY2UgdGhlcmUuLi4uCgpgYGB7ciBEaWZmZXJlbnQgd2F5fQpnZl9saW5lKHByZWQgfiB4MSB8IG1vZGVsLCBjb2xvciA9ICB+IHgyLCBncm91cCA9IH4geDIsIGRhdGEgPSBncmlkKSAlPiUgZ2ZfcmVmaW5lKHNjYWxlX2NvbG9yX2Rpc3RpbGxlcihwYWxldHRlID0gNykpCgpnZl9saW5lKHByZWQgfiB4MiB8fiBtb2RlbCwgY29sb3IgPSB+IHgxLCBncm91cCA9IH4geDEsIGRhdGEgPSBncmlkKQpgYGAKCkxldCdzIGxvb2sgYXQgdGhlIHJlc2lkdWFscy4uLgpgYGB7ciBSZXNpZHVhbHMgZm9yIENvbnRpbnVvdXMgaW50ZXJhY3RpbmcgdmFyaWFibGVzfQpzaW00ICU+JSAKICBnYXRoZXJfcmVzaWR1YWxzKG1vZDEsIG1vZDIpICU+JSAKICBnZl9wb2ludChyZXNpZCB+IHgxfG1vZGVsIH4geDIsIGNvbG9yID0gfngyLCBkYXRhID0gc2ltNCkKCiMgV2hhdCBwbG90IGNhbiB3ZSB1c2UgdG8gc2hvdyB3aGljaCBtb2RlbCBpcyBiZXR0ZXI/CnNpbTQgJT4lIAogIGdhdGhlcl9yZXNpZHVhbHMobW9kMSwgbW9kMikgJT4lIAogIGdmX3BvaW50KG1lYW4oYWJzKHJlc2lkKSl+IHgxIHwgbW9kZWwgfiB4MiwgY29sb3IgPSB+IHgyLCBkYXRhID0gLikKIyBORUVEUyBNT1JFIElNQUdJTkFUSU9OIEFORCBNT1JFIFdPUkshIQogIApgYGAKCiMjIFRyYW5zZm9ybWF0aW9uIHdoaWxlIE1vZGVsbGluZwoKRGF0YSB2YXJpYWJsZXMgY2FuIGFsc28gYmUgYWxnZWJyYWljYWxseSB0cmFuc2Zvcm1lZCB3aGlsZSBwdXR0aW5nIHRoZW0gaW50byB0aGUgbW9kZWwuIEFjdHVhbCBhcml0aG1ldGljIG9wZXJhdG9ycyBsaWtlIGArYCBhbmQgYCpgIHNob3VsZCBiZSB3cmFwcGVkIGluIGBJKClgIHRvIGVuc3VyZSB0aGF0IHRoZXkgYXJlIGludGVycHJldGVkIGNvcnJlY3RseS4gSXQgaXMgYWx3YXlzIGdvb2QgdG8gY2hlY2sgd2l0aCBgbW9kZWxfbWF0cml4YCB3aGF0IHRoZSBtb2RlbCBpcyBkb2luZywgc28gdGhhdCB3ZSBrbm93IHdoYXQgd2UgYXJlIGdldHRpbmcuIAo+IE5vdGUgd2UgY2FuIGRvIHRoZSBtb2RlbGxpbmcgaXRzZWxmIGluc2lkZSB0aGUgYCBtb2RlbF9tYXRyaXhgIGNvbW1hbmQhCgpgYGB7ciBUcmFuc2Zvcm1hdGlvbnMgaW4gTW9kZWxzfQpkZiA8LSB0cmliYmxlKH55LCB+eCwgMSwxLDIsMiwzLDMpCgptb2RlbF9tYXRyaXgoZGYsIHkgfiB4XjIgKyB4KQojIFRoaXMgdXNlcyB0aGUgV2lsa2luc29uLVJvZ2VycyBOb3RhdGlvbiAhIQoKbW9kZWxfbWF0cml4KGRmLCB5IH4gSSh4XjIpICsgeCkKIyBDYW4gYWxzbyB1c2UgSSh4XjIgKyB4KQpgYGAKClRoZXJlIGFyZSBtYW55IHRyYW5zZm9ybWF0aW9ucyBwb3NzaWJsZSBVc2luZyBUYXlsb3IncyBzZXJpZXMgaXMgb25lIHdheQpgYGB7ciBUYXlsb3Igc2VyaWVzfQptb2RlbF9tYXRyaXgoZGYsIHkgfiBwb2x5KHgsIDIpKQpgYGAKCmBwb2x5YCBmaXRzIHRoZSBkYXRhIHdlbGwgd2l0aGluIHRoZSByYW5nZTsgb3V0c2lkZSwgd2hlbiBpdCBpcyBleHRyYXBvbGF0aW5nLCBpdCBtYXkgbWF5IHNob290IG9mZiB0byBpbmZpbml0eS4gCkluIHRoaXMgY2FzZSBpdCBpcyBiZXR0ZXIgdG8gdXNlIGBuYXR1cmFsIHNwbGluZXNgLCB3aGljaCBpcyBzb21ld2hhdCBiZXR0ZXIsIHRob3VnaCBpdCBzdGlsbCBtYWtlcyBlcnJvcnMgb3V0c2lkZSB0aGUgZGF0YSByYW5nZS4gCgpgYGB7ciBTcGxpbmVzfQpsaWJyYXJ5KHNwbGluZXMpCm1vZGVsX21hdHJpeChkZiwgeSB+IG5zKHgsIDIpKQpgYGAKCkxldCB1cyBtb2RlbCBgbm9ubGluZWFyIGRhdGFgLiAKCmBgYHtyIE1vZGVsbGluZyBub25saW5lYXIgZGF0YX0Kc2ltNSA8LSB0aWJibGUoeCA9IHNlcSgwLCAzLjUgKiBwaSwgbGVuZ3RoID0gNTApLAogICAgICAgICAgICAgICB5ID0gNCAqIHNpbih4KSArIHJub3JtKGxlbmd0aCh4KSkpCmdmX3BvaW50KHkgfiB4LCBkYXRhID0gc2ltNSkKCiMgV2UgY2FuIGZpdCBtdWx0aXBsZSBtb2RlbHMgdG8gdGhpcyBkYXRhCm1vZDEgPC0gbG0oeSB+IG5zKHgsIDEpLCBkYXRhID0gc2ltNSkKbW9kMiA8LSBsbSh5IH4gbnMoeCwgMiksIGRhdGEgPSBzaW01KQptb2QzIDwtIGxtKHkgfiBucyh4LCAzKSwgZGF0YSA9IHNpbTUpCm1vZDQgPC0gbG0oeSB+IG5zKHgsIDQpLCBkYXRhID0gc2ltNSkKbW9kNSA8LSBsbSh5IH4gbnMoeCwgNSksIGRhdGEgPSBzaW01KQoKZ3JpZCA8LSBzaW01ICU+JSAKICBkYXRhX2dyaWQoeCA9IHNlcV9yYW5nZSh4LG4gPSA1MCxleHBhbmQgPSAwLjEpKSAlPiUgCiAgZ2F0aGVyX3ByZWRpY3Rpb25zKG1vZDEsbW9kMixtb2QzLG1vZDQsbW9kNSwgLnByZWQgPSAieSIpCgojIFBsb3R0aW5nIHRoZSA1IG1vZGVscwogZ2ZfcG9pbnQoZGF0YSA9IHNpbTUsIHkgfiB4KSAlPiUgCiAgIGdmX2xpbmUoZGF0YSA9IGdyaWQsIHkgfiB4IHwgbW9kZWwsIGNvbG9yID0gfm1vZGVsKSAKIApgYGAKPiBOb3RpY2UgdGhhdCB0aGUgZXh0cmFwb2xhdGlvbiBvdXRzaWRlIHRoZSByYW5nZSBvZiB0aGUgZGF0YSBpcyBjbGVhcmx5IGJhZC4gVGhpcyBpcyB0aGUgZG93bnNpZGUgdG8gYXBwcm94aW1hdGluZyBhIGZ1bmN0aW9uIHdpdGggYSBwb2x5bm9taWFsLiBCdXQgdGhpcyBpcyBhIHZlcnkgcmVhbCBwcm9ibGVtIHdpdGggZXZlcnkgbW9kZWw6IHRoZSBtb2RlbCBjYW4gbmV2ZXIgdGVsbCB5b3UgaWYgdGhlIGJlaGF2aW91ciBpcyB0cnVlIHdoZW4geW91IHN0YXJ0IGV4dHJhcG9sYXRpbmcgb3V0c2lkZSB0aGUgcmFuZ2Ugb2YgdGhlIGRhdGEgdGhhdCB5b3UgaGF2ZSBzZWVuLiBZb3UgbXVzdCByZWx5IG9uIHRoZW9yeSBhbmQgc2NpZW5jZS4KCgojIyBPdGhlciBNb2RlbCBGYW1pbGllcwoKMS4gKiogR2VuZXJhbGlzZWQgTGluZWFyIG1vZGVsczoqKiBgc3RhdHM6OmdsbSgpYCBleHRlbmQgbGluZWFyIG1vZGVscyB0byBgY291bnRgIG9yIGBiaW5hcnlgIHJlc3BvbnNlIHZhcmlhYmxlcy4gVXNlIGEgZGlmZmVyZW50IG1ldHJpYyBmb3IgZGlzdGFuY2UuCgoyLiAqKiBHZW5lcmFsaXNlZCBBZGRpdGl2ZSBNb2RlbHM6KiogYG1nY3Y6OmdhbSgpYCBjYW4gdXNlIGFyYml0cmFyeSBzbW9vdGggbW9kZWxsaW5nIGZ1bmN0aW9ucyBsaWtlIGAgeSB+IHMoeClgLiBgZ2FtKClgIHdpbGwgZXN0aW1hdGUgdGhlIGZ1bmN0aW9uLiAoUmF0aGVyIGxpa2UgdGhlIHJlZ3Jlc3Npb24gc29mdHdhcmUgSSB1c2VkIGVhcmxpZXIuKSAKCjMuICoqIFBlbmFsaXNlZCBMaW5lYXIgTW9kZWxzOioqIGBnbG1uZXQ6OmdsbW5ldCgpYCBBZGRzIGEgcGVuYWx0eSB2ZWN0b3IgaW4gYHBhcmFtZXRlciBzcGFjZWAgY29ycmVzcG9uZGluZyB0byBkaXN0YW5jZSBvZiB0aGF0IHZlY3RvciBmcm9tIHRoZSBvcmlnaW4uIFRlbmRzIHRvIG1ha2UgbW9kZWxzIGdlbmVyYWxpc2UgYmV0dGVyIHRvIG5ldyBkYXRhc2V0cyBmcm9tIHRoZSBgcG9wdWxhdGlvbmAuIAoKNC4gKiogUm9idXN0IExpbmVhciBNb2RlbHM6KiogYE1BU1M6OnJsbSgpYCB0d2Vha3MgdGhlIGRpc3RhbmNlIG1ldHJpYyB0byBkb3duLXdlaWdodCBkYXRhIHBvaW50cyB0aGF0IGFyZSBmYXIgYXdheSwgaS5lLiBvdXRsaWVycy4gTGVzcyBzZW5zaXRpdmUgdG8gb3V0bGllcnMsIGJ1dCBub3Qgc28gZ29vZCB3aGVuIHRoZXJlIGFyZSAqbm8gb3V0bGllcnMqLgoKNS4gKiogVHJlZXM6KiogRml0IHBpZWNlLXdpc2UgbGluZWFyIG1vZGVscyB0byBzbWFsbGVyIGFuZCBzbWFsbGVyIHBpZWNlcyBvZiBkYXRhICggbGlrZSBhICoqTGluZGVubWF5ZXIgZnJhY3RhbCoqKS4gV29yayBiZXN0IHdoZW4gdXNlZCBpbiBhZ2dyZWdhdGUgbW9kZWxzIGxpa2UgYHJhbmRvbUZvcmVzdDo6cmFuZG9tRm9yZXN0KClgIGFuZCAqKmdyYWRpZW50IGJvb3N0KiogYHhnYm9vc3Q6OnhnYm9vc3QoKWAuCgoKCgoKCgoKCgoKCgoKCgoKCgoKCgoKCgoKCkEgR2VuZXJhbGl6ZWQgTGluZWFyIE1vZGVsIChHTE0vR0xaKSBoZWxwcyByZXByZXNlbnQgdGhlIGRlcGVuZGVudCB2YXJpYWJsZSBhcyBhIGxpbmVhciBjb21iaW5hdGlvbiBvZiBpbmRlcGVuZGVudCB2YXJpYWJsZXMuCiBJbiBpdHMgc2ltcGxlc3QgZm9ybSwgYSBsaW5lYXIgbW9kZWwgc3BlY2lmaWVzIHRoZSAobGluZWFyKSByZWxhdGlvbnNoaXAgYmV0d2VlbiBhIGRlcGVuZGVudCAob3IgcmVzcG9uc2UpIHZhcmlhYmxlIFksIGFuZCBhIHNldCBvZiBwcmVkaWN0b3IgdmFyaWFibGVzLCB0aGUgWCdzLCBzbyB0aGF0CgokJApZID0gYl8wICsgYl8xWF8xICsgYl8yWF8yICsgLi4uICsgYl9rWF9rICArIGUKJCQgCgpJbiB0aGUgR0xacywgdGhlIG1vZGVsIGlzIGFzc3VtZWQgdG8gYmU6CiQkClkgPSBnIChiXzAgKyBiXzFYXzEgKyBiXzJYXzIgKyAuLi4gKyBiX2tYX2sgKSsgZQokJApUaGUgYGludmVyc2VgIG9mIHRoZSBmdW50aW9uIGBnKC4uLilgLCBzYXkgZiguLi4pYCBpcyBjYWxsZWQgdGhlIGBsaW5rIGZ1bmN0aW9uYCwgc28gdGhhdDoKCiQkCmYoXG11X1kpPSBiXzAgKyBiXzFYXzEgKyBiXzJYXzIgKyAuLi4gKyBiX2tYX2sKJCQKCgpHTFpzIHdvcmsgd2hlbiA6CgphKSB0aGUgZGVwZW5kZW50IHZhcmlhYmxlIGhhcyBhIGRpc2NyZXRlL211bHRpbm9taWFsIGRpc3RyaWJ1dGlvbi4gVGhlIGRpc3RyaWJ1dGlvbiBvZiB0aGUgZGVwZW5kZW50IG9yIHJlc3BvbnNlIHZhcmlhYmxlIGNhbiBiZSAoZXhwbGljaXRseSkgbm9uLW5vcm1hbCwgYW5kIGRvZXMgbm90IGhhdmUgdG8gYmUgY29udGludW91cywgaS5lLiwgaXQgY2FuIGJlIGJpbm9taWFsLCBtdWx0aW5vbWlhbCwgb3Igb3JkaW5hbCBtdWx0aW5vbWlhbCAoaS5lLiwgY29udGFpbiBpbmZvcm1hdGlvbiBvbiByYW5rcyBvbmx5KTsgCgpiKSB0aGUgcmVsYXRpb25zaGlwIGJldHdlZW4gICBkZXBlbmRlbnQgYW5kIGluZGVwZW5kZW50IHZhcmlhYmxlIChpLmUuIHRoZSBgbGluayBmdW5jdGlvbmApIGlzIGluaGVyZW50bHkgbm9ubGluZWFyLCBvciBhIHBvd2VyIHJlbGF0aW9uc2hpcCwgZm9yIGV4YW1wbGUuIAoKIyMgVHlwZXMgb2YgYGxpbmsgZnVuY3Rpb25zYCBhbmQgZGlzdHJpYnV0aW9ucyBvZiBgeWAgZGVwZW5kZW50IHZhcmlhYmxlcwoKVmFyaW91cyBsaW5rIGZ1bmN0aW9ucyBjYW4gYmUgY2hvc2VuIGJhc2VkIG9uIHRoZSBhc3N1bWJuZWQgZGlzdHJpYnV0aW9ucyBvZiB0aGUgeSBkZXBlbmRlbnQgdmFyaWFibGU6CgpgYGB7ciBgbGlua2AgZnVuY3Rpb24gdHlwZXMsIGVjaG89RkFMU0UsIGZpZy5oZWlnaHQ9NSwgZmlnLndpZHRoPTZ9CnBsb3QoCnBsYW50dW1sKCIKICBAc3RhcnRtaW5kbWFwCisgYGxpbmtgIGZ1bmN0aW9ucworKyBOb3JtYWwsIEdhbW1hLCBJbnZlcnNlIE5vcm1hbCwgUG9pc3NvbgorKysgSWRlbnRpdHkKKysrKyBgZih6KSA9IHpgCisrKyBMb2cgCisrKysgZih6KSA9IGxvZyh6KQorKysgUG93ZXIgZih6KSA9IHpeYQorKyBCaW5vbWlhbCwgT3JkaW5hbCBNdWx0aW5vbWlhbAorKysgTG9naXQgYGYoeikgPSBsb2coei8oMS16KSkKKysrIFByb2JpdCBgZih6KSA9IGludm5vcm0oeikKKysrIENvbXBsZW1lbnRhcnkgbG9nLWxvZyBgZih6KSA9IGxvZygtbG9nKDEteikpCisrKyBMb2ctbG9nIGBmKHopID0gbG9nKC1sb2coeikpCi0tIE11bHRpbm9taWFsCi0tLSBHZW5lcmFsaXplZCBsb2dpdCAKLS0tLSBmKHoxfHoyLi4uemMpID0gbG9nKHgxLygxLXoxLS4uLi4uLXpjKSkgd2hlcmUgbW9kZWwgaGFzIGBjKzFgIGNhdGVnb3JpZXMKQGVuZG1pbmRtYXAiKSkKYGBgCiMgQ29jYUNvbGEgU2FsZXMgRGF0YSBFeHBsb3JhdGlvbgoKYGBge3IgRURBfQojIFRlbXBlcmF0dXJlIHZzIENvY2FDb2xhIHNhbGVzCmNvbGEgPC0gcmVhZF9jc3YoIi4vY29sYS5jc3YiKQpwZW5hbHR5IDwtIHJlYWRfY3N2KCIuL3BlbmFsdHkuY3N2IikKCnN0cihjb2xhKQpnZl9wb2ludChDb2xhIH4gVGVtcGVyYXR1cmUsIGRhdGEgPSBjb2xhKQpgYGAKCiMjIExpbmVhciBNb2RlbCBGaXR0aW5nCmBgYHtyIExpbmVhciBtb2RlbH0KCm1vZGVsID1sbShkYXRhID0gY29sYSwgQ29sYSB+IFRlbXBlcmF0dXJlKQpnZl9wb2ludChDb2xhIH4gVGVtcGVyYXR1cmUsIGRhdGEgPSBjb2xhKSAlPiUgCiAgZ2ZfYWJsaW5lKGludGVyY2VwdCA9IH5tb2RlbCRjb2VmZmljaWVudHNbMV0sCiAgICAgICAgICAgIHNsb3BlID0gfm1vZGVsJGNvZWZmaWNpZW50c1syXSxkYXRhID0gY29sYSkKCiNDYWxjdWxhdGUgUk1TRQpQcmVkQ29sYSA8LSBwcmVkaWN0KG1vZGVsLCBjb2xhKQpSTVNFIDwtIG1vZGVscjo6cm1zZShtb2RlbCwgY29sYSkKIyMKbW9kZWwKUk1TRQpgYGAKClRoZSBsaW5lYXIgYG1vZGVsYCBpcyBjbGVhcmx5IGluYWRlcXVhdGUgYW5kIG1ha2VzIGZhdWx0eSBwcmVkaWN0aW9ucy4gV2UgdHJ5IHRvIHVzZSBhIGBsb2ctbGluZWFyYCBtb2RlbCBuZXh0LCBzaW5jZSB0aGUgYENvbGFgIHNhbGVzIGZpZ3VyZSBzZWVtcyB0byBoYXZlIGFuIGV4cG9uZW50aWFsIHJlbGF0aW9uc2hpcCB3aXRoIGBUZW1wZXJhdHVyZWAuIFdlIHNlZSB0aGF0OgokJENvbGEgPSBhICogYiBeIHtUZW1wZXJhdHVyZX0gLi4uLkVxbigxKSQkCgo+IFN1Y2ggZ3Jvd3RoIG1vZGVscyBkZXBpY3QgYSB2YXJpZXR5IG9mIHJlYWwgbGlmZSBzaXR1YXRpb25zIGFuZCBjYW4gYmUgbW9kZWxlZCB1c2luZyBsb2ctbGluZWFyIHJlZ3Jlc3Npb24uICBBcGFydCBmcm9tIGV4cG9uZW50aWFsIHJlbGF0aW9uc2hpcCwgbG9nIHRyYW5zZm9ybWF0aW9uIG9uICh0aGUpIGRlcGVuZGVudCB2YXJpYWJsZSBpcyBhbHNvIHVzZWQgd2hlbiBkZXBlbmRlbnQgdmFyaWFibGUgZm9sbG93czogCmEpIGxvZy1ub3JtYWwgZGlzdHJpYnV0aW9uIC0gbG9nLW5vcm1hbCBkaXN0cmlidXRpb24gaXMgZGlzdHJpYnV0aW9uIG9mIGEgcmFuZG9tIHZhcmlhYmxlIHdob3NlIGxvZyBmb2xsb3dzIG5vcm1hbCBkaXN0cmlidXRpb24uIFRodXMsIHRha2luZyBsb2cgb2YgYSBsb2ctbm9ybWFsIHJhbmRvbSB2YXJpYWJsZSBtYWtlcyB0aGUgdmFyaWFibGUgbm9ybWFsbHkgZGlzdHJpYnV0ZWQgYW5kIGZpdCBmb3IgbGluZWFyIHJlZ3Jlc3Npb24uICAKYikgUG9pc3NvbiBkaXN0cmlidXRpb24gLSBQb2lzc29uIGRpc3RyaWJ1dGlvbiBpcyB0aGUgZGlzdHJpYnV0aW9uIG9mIHJhbmRvbSB2YXJpYWJsZSB0aGF0IHJlc3VsdHMgZnJvbSBhIFBvaXNzb24gZXhwZXJpbWVudC4gRm9yIGV4YW1wbGUsIHRoZSBudW1iZXIgb2Ygc3VjY2Vzc2VzIG9yIGZhaWx1cmVzIGluIGEgdGltZSBwZXJpb2QgVCBmb2xsb3dzIFBvaXNzb24gZGlzdHJpYnV0aW9uLiAgCgpUYWtpbmcgYGxvZ2Agb24gYm90aCBzaWRlcyBvZiBFcW4uMToKCiQkbG9nKENvbGEpID0gbG9nKGEpICsgVGVtcGVyYXR1cmUgKiBsb2coYikkJAoKIyMgTG9nIE1vZGVsIEZpdHRpbmcKV2UgdHJhbnNmb3JtIHRoZSBkYXRhIHVzaW5nIGxvZyBhbmQgdGhlbiBmaXQgYSBsaW5lYXIgbW9kZWwgdG8gdGhlIGBsb2ctdHJhbnNmb3JtZWRgIHZhcmlhYmxlcwoKYGBge3IgTG9nLUxpbmVhciBNb2RlbH0KY29sYSA8LSBjb2xhICU+JSBtdXRhdGUobG9nQ29sYSA9IGxvZyhDb2xhKSkKCmxvZ21vZGVsIDwtIGxtKGxvZ0NvbGEgfiBUZW1wZXJhdHVyZSwgZGF0YSA9IGNvbGEpCmxvZ21vZGVsCgojIFBsb3RzCmdmX3BvaW50KGRhdGEgPSBjb2xhLCBsb2dDb2xhflRlbXBlcmF0dXJlKSAlPiUgCiAgZ2ZfYWJsaW5lKGludGVyY2VwdCA9IH5sb2dtb2RlbCRjb2VmZmljaWVudHNbMV0sc2xvcGUgPSB+bG9nbW9kZWwkY29lZmZpY2llbnRzWzJdKQoKIyBQcmVkaWN0aW9ucyBhbmQgUk1TRQpQcmVkTG9nQ29sYSA8LSBwcmVkaWN0KGxvZ21vZGVsLGNvbGEpClJNU0Vsb2cgPC0gbW9kZWxyOjpybXNlKGxvZ21vZGVsLCBjb2xhKQoKUHJlZExvZ0NvbGEKUk1TRWxvZwoKYGBgCkhlbmNlIHRoZSBsb2ctbGluZWFyIG1vZGVsIGlzOgoKJCQgbG9nKENvbGFfaSkgPSAtMC45MDkgKyAwLjE3MiAqIGxvZyhUZW1wZXJhdHVyZV9pKSAkJAoKYGBge3J9CnN0cihQcmVkTG9nQ29sYSkKZ2ZfY29sKGRhdGEgPSBQcmVkTG9nQ29sYSx2YWx1ZSB+IHJvd19udW1iZXIoUHJlZExvZ0NvbGEpKQpgYGAKCgoKCg==